옥트리(Octree)

1. 3차원 공간 분할의 패러다임, 옥트리

1.1 옥트리의 정의와 핵심 원리: 재귀적 8분할 공간 구조

옥트리(Octree)는 3차원 공간을 효율적으로 표현하고 관리하기 위해 설계된 트리(tree) 기반의 자료구조이다.1 그 이름은 ’여덟’을 의미하는 그리스어 ’oct’와 ’tree’의 합성어에서 유래했으며, 이름이 암시하듯 각 내부 노드(internal node)가 정확히 8개의 자식 노드(child node)를 갖는 구조적 특징을 지닌다.1 옥트리의 가장 근본적인 원리는 3차원 공간을 재귀적으로(recursively) 8개의 동일한 부피를 갖는 하위 공간, 즉 옥턴트(octant)로 분할하는 것이다.2

이 계층적 공간 분할 방식은 3차원 데이터를 다루는 다양한 문제 영역에서 핵심적인 역할을 수행한다. 옥트리의 최상위 노드인 루트 노드(root node)는 분석하고자 하는 전체 3차원 공간을 하나의 정육면체 또는 직육면체 경계 상자(bounding box)로 표현한다.4 만약 이 노드가 특정 조건을 만족하지 못하면(예를 들어, 내부에 포함된 데이터의 수가 일정 임계치를 초과하는 경우), 해당 공간은 세 개의 축(X, Y, Z)에 평행한 절단면을 통해 8개의 동일한 크기를 가진 자식 옥턴트로 분할된다.6 이 과정은 각 옥턴트가 설정된 종료 조건을 만족할 때까지 재귀적으로 반복된다. 대표적인 종료 조건으로는 노드에 포함된 객체의 수가 미리 정해진 임계값 이하가 되거나, 트리의 깊이가 최대 허용 깊이에 도달하거나, 노드의 크기가 더 이상 분할할 의미가 없을 정도로 작아지는 경우 등이 있다.2

이러한 재귀적 분할을 통해 옥트리는 데이터가 밀집된 영역은 더 깊고 세밀하게 분할하고, 데이터가 없거나 희소한 영역은 더 큰 노드로 묶어 표현하는 적응형(adaptive) 공간 분할을 구현한다. 이는 3차원 공간 내 데이터의 분포를 효율적으로 반영하여 저장 공간을 절약하고, 후술할 다양한 연산의 효율을 극대화하는 기반이 된다.4

옥트리의 근본적인 힘은 ’공간적 일관성(spatial coherence)’이라는 개념을 효과적으로 활용하는 데 있다. 이는 물리적으로 인접한 객체들이 자료구조 상에서도 가깝게 위치할 가능성이 높다는 원칙이다. 수많은 컴퓨터 그래픽스 및 시뮬레이션 응용 프로그램의 핵심은 특정 지점이나 영역 주변의 객체를 신속하게 찾는 것이다.4 모든 객체 쌍을 일일이 비교하는 선형 탐색(brute-force search) 방식은 객체의 수가 N개일 때 충돌 감지의 경우 O(N2), 단순 검색의 경우 O(N)의 비효율적인 시간 복잡도를 가진다.8 옥트리는 공간을 계층적으로 분할함으로써 이러한 비효율을 극복한다. 특정 쿼리(예: 충돌 검사, 가시성 판단)를 수행할 때, 해당 쿼리 영역과 전혀 겹치지 않는 노드가 발견되면 그 노드에 속한 모든 하위 노드와 객체들은 추가적인 검사 없이 즉시 탐색 과정에서 배제된다. 이 ‘가지치기(pruning)’ 과정은 물리적으로 멀리 떨어진 객체들 간의 상호작용을 검사할 필요가 없다는 공간적 일관성 가정을 자료구조로 구현한 것이며, 이를 통해 불필요한 연산을 원천적으로 차단하여 성능을 획기적으로 향상시킨다.11

1.2 역사적 배경과 발전 과정

옥트리의 개념은 1980년 렌셀러 폴리테크닉 대학교(Rensselaer Polytechnic Institute)의 도널드 미거(Donald Meagher)에 의해 3차원 컴퓨터 그래픽스 분야에 선구적으로 도입되었다.2 그의 기술 안내서 “Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer“는 옥트리를 이용해 임의의 복잡한 3차원 객체를 표현하고, 조작하며, 화면에 표시하는 새로운 기법의 기틀을 마련했다.2

초기 옥트리 연구는 주로 3차원 객체의 효율적인 저장 방식과 불리언 연산(Boolean operations)의 구현에 집중되었다. 옥트리 인코딩을 사용하면 복잡한 객체 간의 합집합(union), 교집합(intersection), 차집합(difference) 연산을 트리 순회를 통한 단순한 정수 연산만으로 수행할 수 있었다.13 이는 부동소수점 연산이 비쌌던 당시의 컴퓨팅 환경에서 매우 큰 장점이었다. 또한, 객체의 표면적에 비례하는 메모리만으로 객체를 표현할 수 있어 저장 효율성도 높았다.13

시간이 흐르면서 옥트리의 응용 범위는 기하학적 모델링을 넘어 훨씬 더 넓은 분야로 확장되었다. 1988년 Gervautz와 Purgathofer는 옥트리를 이미지의 색상 양자화(color quantization) 문제에 적용하는 알고리즘을 발명했다.2 이는 옥트리가 단순히 공간 좌표뿐만 아니라, RGB 색상 공간과 같은 추상적인 3차원 데이터를 구조화하는 데에도 효과적임을 보여준 사례이다. 이후 옥트리는 빠른 공간 쿼리 성능을 바탕으로 컴퓨터 게임 엔진의 실시간 충돌 감지, 광선 추적(ray tracing)의 가속 구조, 지리 정보 시스템(GIS)에서의 대규모 공간 데이터 인덱싱, 로보틱스 분야의 환경 인식 및 지도 작성(mapping) 등 다양한 핵심 기술의 기반으로 자리 잡게 되었다.4 이처럼 옥트리는 3차원 데이터를 다루는 거의 모든 분야에서 그 효율성과 유연성을 인정받으며 지속적으로 발전해왔다.

1.3 쿼드트리와의 관계: 2차원에서 3차원으로의 확장

옥트리는 2차원 공간 분할에 사용되는 자료구조인 쿼드트리(Quadtree)의 직접적인 3차원 확장판으로 이해할 수 있다.1 쿼드트리는 2차원 평면을 재귀적으로 4개의 동일한 사분면(quadrant)으로 분할하며, 각 내부 노드는 4개의 자식 노드를 가진다.17 옥트리는 이 원리를 3차원 공간으로 확장하여, 공간을 8개의 옥턴트(octant)로 분할하고 각 내부 노드가 8개의 자식 노드를 갖도록 한 것이다.19 즉, 쿼드트리가 X축과 Y축에 평행한 두 개의 분할선을 사용하는 반면, 옥트리는 X, Y, Z축에 평행한 세 개의 분할 평면을 사용한다.

이러한 차원적 확장은 단순히 자식 노드의 수가 4개에서 8개로 늘어나는 것 이상의 의미를 내포한다. 3차원 공간의 복잡성으로 인해, 부피를 가진 객체가 여러 옥턴트에 동시에 걸치는(straddling) 경우가 2차원보다 훨씬 더 빈번하고 복잡하게 발생한다. 이는 객체의 삽입, 삭제, 검색 알고리즘을 설계할 때 중요한 고려사항이 되며, 알고리즘의 복잡성을 증가시키는 주요 요인으로 작용한다.

쿼드트리와 옥트리는 더 높은 차원으로도 일반화될 수 있다. d차원 공간을 2d개의 하위 공간으로 분할하는 이러한 자료구조를 통칭하여 하이퍼옥트리(hyperoctree) 또는 오르트리(orthtree)라고 부른다.20 그러나 차원이 증가함에 따라 자식 노드의 수가 기하급수적으로 늘어나기 때문에(2d), 4차원 이상에서는 메모리 비효율성과 관리의 복잡성으로 인해 옥트리 방식의 직접적인 확장은 잘 사용되지 않는다. 대신, 각 단계에서 하나의 축으로만 공간을 이진 분할하는 k-d 트리와 같은 다른 접근법이 고차원 공간에서 더 선호되는 경향이 있다.20

2. 옥트리의 수학적 표현과 구현

2.1 노드의 구조: 경계 상자, 자식 포인터, 데이터

옥트리를 구성하는 각 노드는 세 가지 핵심 요소로 이루어진다: 공간적 범위를 정의하는 경계 상자, 계층 구조를 형성하는 자식 포인터, 그리고 실제 정보를 담는 데이터 필드이다.

첫째, 각 옥트리 노드는 자신이 표현하는 3차원 공간 영역을 명확히 정의하기 위한 축 정렬 경계 상자(Axis-Aligned Bounding Box, AABB)를 가진다.6 이 경계 상자는 해당 노드가 관할하는 공간의 범위를 나타내며, 일반적으로 공간의 최소점 좌표 P_{min} = (x_{min}, y_{min}, z_{min})과 최대점 좌표 P_{max}=(x_{max},y_{max},z_{max}) 두 개의 3차원 벡터로 정의된다.2 이 AABB는 옥트리 순회 중 특정 영역과의 교차 여부를 판단하는 데 사용되어 효율적인 가지치기를 가능하게 하는 핵심 요소이다.

둘째, 노드의 종류에 따라 자식 노드와의 관계가 결정된다. 공간을 더 분할하는 내부 노드(Internal Node)는 8개의 자식 노드를 가리키는 포인터(또는 이에 상응하는 인덱스) 배열을 포함한다.4 반면, 더 이상 분할되지 않는 트리의 말단에 위치한 리프 노드(Leaf Node)는 자식 포인터를 갖지 않으며(NULL), 대신 실제 데이터를 저장하는 역할을 한다.21 이처럼 자식 포인터의 유무로 내부 노드와 리프 노드를 간단히 구분할 수 있다.21

셋째, 노드에 저장되는 데이터는 옥트리의 응용 분야에 따라 그 형태가 매우 다양하다. 예를 들어, 포인트 클라우드 처리용 옥트리의 리프 노드는 해당 공간에 속하는 점들의 좌표 리스트나 인덱스를 저장한다.22 게임 엔진의 충돌 감지 시스템에서는 해당 노드와 교차하는 게임 객체에 대한 참조나 포인터 리스트를 저장한다.8 볼륨 렌더링(volume rendering)에서는 복셀(voxel)의 색상, 밀도, 재질과 같은 속성 정보를 저장할 수 있다.24 이처럼 옥트리는 그 자체로 범용적인 공간 분할 프레임워크를 제공하며, 각 노드에 어떤 데이터를 저장하느냐에 따라 특정 문제에 특화된 자료구조로 기능한다.

2.2 옥턴트(Octant) 인덱싱 논리와 좌표 계산

부모 노드가 나타내는 공간을 8개의 자식 옥턴트로 분할하는 과정은 체계적인 규칙에 따라 이루어진다. 분할의 기준은 부모 노드 경계 상자의 중심점(center point) C = (c_x, c_y, c_z)이다. 이 중심점을 통과하는 세 개의 축에 평행한 평면들(x=c_x, y=c_y, z=c_z)이 부모 공간을 정확히 8개의 동일한 크기를 가진 직육면체로 나눈다.6

특정 좌표 P = (p_x, p_y, p_z)가 8개의 옥턴트 중 어느 곳에 속하는지를 결정하는 인덱싱은 중심점과의 좌표 비교를 통해 매우 효율적으로 수행될 수 있다. 각 축에 대한 비교 결과를 비트(bit)로 표현하여 조합하는 방식이 널리 사용된다. 예를 들어, 다음과 같은 규칙을 적용할 수 있다 2:

1. p_x>c_x 이면 X축 비트를 1로, 아니면 0으로 설정한다.
2. p_y>c_y 이면 Y축 비트를 1로, 아니면 0으로 설정한다.
3. p_z>c_z 이면 Z축 비트를 1로, 아니면 0으로 설정한다.

이 세 비트를 특정 순서(예: ZYX)로 조합하여 3비트 정수를 만들면 0부터 7까지의 고유한 옥턴트 인덱스를 얻을 수 있다. C++ 스타일의 코드로 표현하면 다음과 같다:

int octantIndex = 0;
if (point.x > center.x) octantIndex |= 1; // 001
if (point.y > center.y) octantIndex |= 2; // 010
if (point.z > center.z) octantIndex |= 4; // 100

이러한 비트 연산을 통한 인덱싱은 매우 빠르며, 재귀적인 삽입 및 탐색 과정에서 경로를 결정하는 데 핵심적으로 사용된다.

일단 옥턴트 인덱스가 결정되면, 해당 자식 노드의 경계 상자는 부모 노드의 경계 상자와 중심점을 이용해 간단히 계산할 수 있다. 예를 들어, 부모 노드의 경계가 P_{min}과 P_{max}이고 중심점이 C일 때, 각 옥턴트의 경계 상자는 다음과 같이 정의된다 26:

• 옥턴트 0 (—): P_\min 에서 C 까지
• 옥턴트 1 (+–): (c_x,y_\min,z_\min) 에서 (x_\max,c_y,c_z) 까지
• …
• 옥턴트 7 (+++): C 에서 P_\max 까지

이러한 계산은 재귀적 분할 과정에서 각 노드의 공간적 범위를 명확히 정의하는 기반이 된다.

2.3 구현 방식 비교: 포인터 기반 옥트리 대 선형 옥트리

옥트리를 메모리상에 구현하는 방식은 크게 두 가지로 나뉘며, 각각은 개념적 단순성과 하드웨어 수준의 성능 사이에서 뚜렷한 트레이드오프를 보인다.

포인터 기반(Pointer-based) 옥트리는 가장 직관적이고 전통적인 구현 방식이다.15 이 방식에서는 각 노드를 클래스나 구조체로 정의하고, 내부 노드는 8개의 자식 노드를 가리키는 포인터(또는 참조)를 멤버 변수로 가진다.27 재귀적인 알고리즘(삽입, 탐색 등)을 코드 상에 직접적으로 표현하기 용이하여 구현이 비교적 간단하다. 또한, 트리의 일부만 동적으로 확장하거나 축소하는 것이 유연하다는 장점이 있다. 그러나 이 방식은 현대 컴퓨터 아키텍처의 관점에서 볼 때 몇 가지 심각한 성능적 단점을 내포한다. 동적 메모리 할당(new 또는 malloc)을 통해 노드를 생성하면, 각 노드가 메모리 상의 서로 떨어진 위치에 흩어져 배치될 수 있다(memory fragmentation).29 트리 순회 시 이러한 포인터들을 따라가는 과정은 불규칙하고 예측 불가능한 메모리 접근 패턴(random memory access)을 유발하며, 이는 CPU 캐시 미스(cache miss)를 빈번하게 발생시킨다.27 캐시 미스는 CPU 파이프라인을 정체시켜 이론적인 알고리즘의 효율성에도 불구하고 실제 실행 시간을 크게 저하시키는 주된 원인이 된다.

선형(Linear) 옥트리, 또는 포인터리스(Pointerless) 옥트리는 이러한 하드웨어 비친화적 문제를 해결하기 위해 고안된 대안적 구현 방식이다.31 이 방식의 핵심 아이디어는 트리의 전체 구조, 특히 포인터를 이용한 부모-자식 관계를 명시적으로 저장하지 않는 것이다. 대신, 데이터가 포함된 리프 노드들만을 리스트나 배열 형태의 연속된 메모리 공간에 저장한다.32 각 리프 노드의 3차원 공간상 위치와 크기(깊이)는 모튼 코드(Morton code)와 같은 공간 채움 곡선(space-filling curve)을 사용하여 하나의 정수 값으로 인코딩된다.33 모튼 코드는 다차원 공간의 좌표를 1차원 값으로 매핑하면서 공간적 지역성(spatial locality)을 최대한 보존하는 특성을 가진다. 즉, 3D 공간에서 가까운 두 점은 모튼 코드로 변환된 1D 값도 가까울 가능성이 높다.

이러한 특성 덕분에, 리프 노드들을 모튼 코드 순서로 정렬하여 배열에 저장하면 물리적으로 인접한 노드들이 메모리 상에서도 인접하게 배치된다.32 이는 데이터 지역성을 극대화하여 트리 순회나 범위 탐색 시 순차적인 메모리 접근을 유도하고, 결과적으로 CPU 캐시 히트율(cache hit rate)을 극적으로 향상시킨다.29 또한, 포인터 저장에 필요한 메모리 오버헤드가 전혀 없으므로 매우 압축적인 표현이 가능하다.35 특정 노드를 찾는 작업은 정렬된 모튼 코드 배열에 대한 이진 탐색으로

O(logL) (L은 리프 노드의 수) 시간에 수행할 수 있다.32 그러나 선형 옥트리는 동적인 데이터의 삽입 및 삭제가 발생할 때마다 정렬된 배열을 갱신해야 하므로 포인터 기반 방식보다 업데이트 비용이 더 클 수 있다는 단점이 있다.36

결론적으로, 옥트리 구현 방식의 선택은 단순한 자료구조 설계를 넘어, 기반 하드웨어 아키텍처의 특성을 얼마나 잘 활용할 것인가에 대한 깊은 이해를 요구한다. 개념적 명확성과 구현의 용이성이 중요하다면 포인터 기반 방식이 적합할 수 있지만, 대규모 데이터셋을 다루며 극한의 성능을 추구하는 현대의 고성능 컴퓨팅 환경, 특히 병렬 처리가 중요한 GPU 환경에서는 선형 옥트리가 제공하는 하드웨어 친화적 특성이 훨씬 더 큰 이점을 제공한다.29

3. 핵심 연산 알고리즘 분석

3.1 구축 (Construction)

옥트리를 생성하는 과정, 즉 구축은 주어진 3차원 데이터셋을 계층적 구조로 조직화하는 첫 단계이다. 구축 방식은 크게 하향식과 상향식으로 나눌 수 있다.

하향식(Top-Down) 구축은 가장 일반적이고 직관적인 방법이다.15 이 접근법은 전체 데이터 공간을 감싸는 하나의 거대한 경계 상자를 루트 노드로 설정하는 것에서 시작한다. 그 후, 이 루트 노드부터 재귀적인 분할 과정을 수행한다. 각 노드에 대해, 미리 정의된 종료 조건(termination condition)을 만족하는지 검사한다. 만약 조건을 만족하지 않으면, 해당 노드의 공간을 8개의 자식 옥턴트로 분할하고, 노드에 포함된 데이터들을 각각의 자식 노드로 재분배한다. 이 과정은 모든 리프 노드가 종료 조건을 만족할 때까지 계속된다.

하향식 구축의 핵심은 언제 분할을 멈출 것인지를 결정하는 종료 조건이다. 이 조건은 옥트리의 최종 구조와 성능에 직접적인 영향을 미치며, 주로 다음 세 가지 기준이 단독 또는 조합되어 사용된다:

1. 객체 수 임계값: 노드 내에 포함된 객체(점, 폴리곤 등)의 수가 미리 정해진 임계값(예: 8개 또는 16개) 이하로 떨어지면 더 이상 분할하지 않는다.2 이는 데이터가 희소한 영역에서 불필요한 분할을 막아준다.
2. 최대 깊이: 트리의 깊이가 사전에 정의된 최대 허용 깊이(max depth)에 도달하면 분할을 중단한다.2 이는 트리가 무한정 깊어지는 것을 방지하여 메모리 사용량을 제어하고, 최악의 경우 탐색 성능을 보장하는 역할을 한다.
3. 최소 노드 크기: 노드의 경계 상자 한 변의 길이가 특정 최소값 이하로 작아지면 분할을 멈춘다.2 이는 나노미터 크기의 매우 작은 객체나 부동소수점 정밀도 문제로 인해 분할이 무한히 일어나는 것을 방지한다.

상향식(Bottom-Up) 구축은 하향식과는 반대 방향으로 진행된다.15 이 방식은 가장 작은 단위의 데이터(예: 개별 포인트 또는 복셀)를 각각 리프 노드로 간주하는 것에서 시작한다. 그 후, 인접한 8개의 노드 그룹을 찾아 이들을 자식으로 하는 부모 노드를 생성하며 병합(merge)하는 과정을 반복한다. 이 과정은 모든 노드가 단일 루트 노드 아래에 통합될 때까지 계속된다. 상향식 접근법은 주로 이미 복셀화된 데이터나 포인트 클라우드로부터 옥트리를 생성하는 경우에 고려될 수 있으며, 때로는 하향식과 결합된 하이브리드 방식으로 사용되기도 한다.15

3.2 삽입 (Insertion)

새로운 데이터 객체를 기존에 구축된 옥트리에 추가하는 삽입 연산은 하향식 구축 과정과 유사한 재귀적 탐색을 기반으로 한다.

삽입 과정은 루트 노드에서 시작한다.3 삽입하려는 객체의 위치를 기반으로, 이 객체가 속해야 할 8개의 자식 옥턴트 중 하나를 결정한다. 그 후 해당 자식 노드로 이동하여 동일한 과정을 반복하며, 트리를 따라 아래로 내려간다.38 이 재귀적 탐색은 리프 노드에 도달할 때까지 계속된다.

리프 노드에 도달하면, 해당 객체를 리프 노드가 관리하는 데이터 목록에 추가한다. 객체를 추가한 후, 리프 노드가 분할 조건을 만족하는지(즉, 객체 수가 임계값을 초과하고 최대 깊이에 도달하지 않았는지) 확인한다. 만약 분할이 필요하다면, 해당 리프 노드는 내부 노드로 역할이 변경된다. 이어서 8개의 새로운 자식 리프 노드가 생성되고, 기존에 부모 노드에 있던 모든 객체(새로 삽입된 객체 포함)들은 각각의 위치에 따라 새로운 8개의 자식 노드로 재분배된다.15

부피를 가진 객체 처리는 옥트리 알고리즘의 복잡성과 성능을 결정하는 핵심적인 도전 과제이다. 점(point) 데이터는 명확하게 하나의 노드에만 속하지만, 폴리곤, 구(sphere), 경계 상자 등 부피를 가진 기하학적 객체는 필연적으로 여러 옥턴트의 경계에 걸칠 수 있다.9 이 ’경계 문제(boundary problem)’를 해결하는 방식은 메모리 사용량, 쿼리 속도, 업데이트 비용 간의 중요한 트레이드오프를 결정한다. 주요 처리 전략은 다음과 같다 9:

1. 객체 분할(Object Splitting): 객체를 옥턴트 경계 평면을 기준으로 여러 조각으로 자른 후, 각 조각을 해당하는 자식 노드에 개별적으로 삽입하는 가장 정확한 방식이다. 그러나 삼각형-상자 교차 및 절단과 같은 기하학적 연산은 계산 비용이 매우 높고, 데이터 관리(분할된 조각들의 추적 등)를 복잡하게 만든다.9
2. 중복 참조(Duplicate References): 객체가 걸쳐 있는 모든 자식 노드에 해당 객체에 대한 참조(포인터)를 저장하는 가장 간단한 방식이다. 구현은 용이하지만, 하나의 객체가 여러 노드에 존재하게 되므로 저장 공간이 낭비되고, 쿼리(특히 광선 추적) 시 동일한 객체에 대해 불필요한 중복 교차 검사를 수행하게 되어 성능 저하를 유발할 수 있다.9 또한, 모든 객체가 새로 생성된 특정 자식 노드에 계속 걸치는 최악의 경우, 최대 깊이에 도달할 때까지 불필요한 분할이 무한히 반복될 수 있다.9
3. 부모 노드 저장(Promotion to Parent): 객체가 여러 자식 노드에 걸치는 경우, 해당 객체를 자식 노드로 내리지 않고 현재의 부모 노드에 그대로 저장하는 방식이다. 이 전략은 삽입 과정을 단순화하고 중복 저장을 피할 수 있지만, 트리의 상위 레벨(내부 노드)에 많은 객체가 쌓이게 되어 공간 분할의 이점을 약화시킨다. 쿼리 시 내부 노드에 도달했을 때, 자식 노드뿐만 아니라 해당 내부 노드에 저장된 객체들도 모두 검사해야 하므로 탐색 효율이 떨어질 수 있다.9 이러한 딜레마를 해결하기 위해, 노드의 경계를 가상으로 확장하여 경계 문제를 완화하는 ’느슨한 옥트리(Loose Octrees)’와 같은 변종 기법이 제안되기도 했다.41

3.3 탐색 (Search) 및 순회 (Traversal)

옥트리의 진정한 가치는 효율적인 탐색 및 순회 연산에서 드러난다. 공간적 계층 구조를 활용하여 방대한 탐색 공간을 효과적으로 가지치기할 수 있다.

• 점 탐색(Point Location): 주어진 3차원 좌표 P를 포함하는 리프 노드를 찾는 가장 기본적인 연산이다. 루트 노드에서 시작하여, P의 좌표와 현재 노드의 중심점을 비교하여 8개의 자식 노드 중 어느 방향으로 내려가야 할지 결정한다. 이 과정을 리프 노드에 도달할 때까지 재귀적으로 반복한다.15
• 범위 탐색(Range Search): 특정 범위(예: 경계 상자, 구)와 겹치는 모든 객체를 찾는 연산이다. 이 연산은 깊이 우선 탐색(DFS)이나 너비 우선 탐색(BFS)과 같은 트리 순회 알고리즘을 기반으로 한다. 재귀적으로 트리를 순회하면서, 현재 방문 중인 노드의 경계 상자가 주어진 쿼리 범위와 전혀 겹치지 않는 경우, 해당 노드의 모든 하위 트리는 더 이상 탐색할 필요가 없으므로 건너뛴다(pruning). 만약 노드가 범위와 부분적으로 또는 완전히 겹친다면, 자식 노드들로 재귀 호출을 계속하거나, 리프 노드일 경우 해당 노드에 포함된 객체들을 검사하여 결과 목록에 추가한다.11
• 최근접 이웃 탐색(Nearest Neighbor Search, NNS): 특정 지점 Q에서 가장 가까운 이웃 객체(또는 k개의 이웃, k-NN)를 찾는 연산이다. 이는 범위 탐색보다 복잡하며, 보통 우선순위 큐(priority queue)와 같은 자료구조를 함께 사용하여 최적화한다. 트리를 순회하면서, 쿼리 지점 Q로부터 더 가까운 노드를 우선적으로 방문한다. 현재까지 찾은 가장 가까운 이웃과의 거리(최소 거리)를 유지하고, 만약 방문하려는 노드의 경계 상자까지의 거리가 이 최소 거리보다 멀다면, 해당 노드와 그 하위 트리는 탐색에서 제외할 수 있다.11 PCL(Point Cloud Library)과 같은 전문 라이브러리는 k-NN 탐색과 특정 반경 내의 모든 이웃을 찾는 반경 탐색(Radius Search)을 위한 고도로 최적화된 옥트리 구현을 제공한다.44
• 광선 투사(Ray Casting) 및 절두체(Frustum) 테스트: 이들은 컴퓨터 그래픽스에서 특히 중요한 순회 방식이다. 광선 추적에서는 광선이 통과하는 노드들만을 순서대로 방문하여 교차 검사 횟수를 최소화한다.6 렌더링 시에는 카메라의 시야각을 나타내는 절두체(frustum)와 교차하는 노드들만 방문하여 보이지 않는 객체들을 효율적으로 제거(culling)한다.8

3.4 삭제 (Deletion) 및 동적 갱신

정적인 데이터뿐만 아니라 객체가 움직이거나 사라지는 동적인 환경을 지원하기 위해서는 효율적인 삭제 및 갱신 메커니즘이 필수적이다.

객체 삭제는 먼저 해당 객체를 포함하고 있는 리프 노드를 탐색하여 찾아낸 후, 그 노드의 데이터 목록에서 해당 객체를 제거하는 것으로 시작된다. 객체 삭제 후에는 트리의 최적화를 위해 노드 병합(Node Merging) 과정을 고려할 수 있다. 만약 한 내부 노드의 모든 자식 노드(8개의 형제 노드)에 포함된 객체의 총 수가 분할 임계값 이하로 줄어든다면, 이 8개의 자식 노드들을 모두 제거하고, 남아있는 모든 객체들을 부모 노드로 옮긴 후, 부모 노드를 새로운 리프 노드로 만드는 것이다.15 이 병합 과정은 트리의 상위 레벨로 재귀적으로 전파될 수 있으며, 불필요하게 깊고 복잡해진 트리를 단순화하여 메모리를 절약하고 탐색 효율을 유지하는 데 도움을 준다.

객체들이 지속적으로 움직이는 고도로 동적인 환경(예: 실시간 물리 시뮬레이션, 다수의 플레이어가 움직이는 게임)에서는 옥트리를 갱신하는 전략이 매우 중요하다.

• 전체 재구축(Trash & Rebuild): 가장 간단한 접근법은 매 프레임(또는 몇 프레임마다) 기존 옥트리를 완전히 폐기하고 모든 객체를 사용하여 처음부터 새로 구축하는 것이다.8 이 방법은 구현이 간단하고 항상 최적에 가까운 트리를 유지할 수 있다는 장점이 있다. 그러나 매번 대규모 메모리 할당과 해제가 반복되어 오버헤드가 크고, 대부분의 객체가 움직이지 않는 상황에서는 엄청난 CPU 시간 낭비를 초래한다.8
• 증분 갱신(Incremental Update): 더 효율적인 방법은 움직인 객체만 식별하여 처리하는 것이다. 각 프레임마다 움직인 객체를 이전 위치의 노드에서 삭제하고, 새로운 위치에 다시 삽입하는 방식이다. 이 방법은 변화가 적은 씬에서 재구축보다 훨씬 빠르지만, 객체가 노드 경계를 자주 넘나들 경우 삽입/삭제 연산이 빈번하게 발생하여 여전히 비효율적일 수 있다.
• 동적 옥트리 구조: 최근 연구에서는 이러한 동적 환경에 특화된 옥트리 변종들이 제안되고 있다. 예를 들어, i-Octree는 점진적 삽입, 개별 점 삭제, 그리고 특정 공간 영역 내의 모든 점을 한 번에 삭제하는 박스 단위 삭제(box-wise delete)와 같은 동적 연산을 매우 효율적으로 지원하도록 설계되었다.47 이러한 구조는 실시간 SLAM이나 대규모 동적 시뮬레이션과 같이 지속적인 데이터 스트림을 처리해야 하는 응용 분야에서 그 가치를 발휘한다.

4. 성능 분석: 시간 및 공간 복잡도

4.1 주요 연산의 점근적 복잡도 분석

옥트리의 성능은 이론적으로 시간 복잡도와 공간 복잡도를 통해 분석될 수 있다. 여기서 N은 옥트리에 저장된 총 객체의 수를 의미한다.

• 구축 (Construction): N개의 객체를 사용하여 옥트리를 처음부터 구축하는 과정의 평균 시간 복잡도는 O(N \log N)이다.2 이는 각 객체를 트리에 삽입하는 데 평균적으로 O(\log N)의 시간이 소요되고, 이 과정을

N개의 모든 객체에 대해 반복하기 때문이다. 여기서 logN 항은 데이터가 비교적 균일하게 분포하여 트리의 깊이가 logN에 비례하는 균형 잡힌 상태를 가정할 때 성립한다.

• 삽입 (Insertion), 삭제 (Deletion), 탐색 (Search): 균형 잡힌 옥트리에서 단일 객체를 삽입, 삭제하거나 특정 위치의 노드를 탐색하는 연산의 평균 시간 복잡도는 모두 O(\log N)이다.2 이 복잡도는 연산이 트리의 루트에서 리프까지의 경로를 따라 진행되며, 그 경로의 길이는 트리의 깊이에 비례하기 때문에 발생한다.

• 범위 탐색 (Range Query) 및 반경 탐색 (Radius Search): 특정 공간 범위 내에 있는 모든 객체를 찾는 연산의 시간 복잡도는 일반적으로 O(\log N + K)로 표현된다.2 여기서

K는 쿼리 결과로 반환되는 객체의 수이다. O(logN) 항은 쿼리 범위와 겹치는 첫 번째 노드들을 찾기 위해 트리를 탐색하는 데 필요한 시간을 나타내고, O(K) 항은 결과에 포함되는 객체들을 수집하고 보고하는 데 필요한 시간을 나타낸다.

• 공간 복잡도 (Space Complexity): 옥트리가 차지하는 메모리 공간은 최상의 경우(데이터가 매우 밀집된 경우) O(1)에 가까울 수 있으며, 평균적으로는 O(N)에 비례한다. 각 객체가 하나의 리프 노드에 저장되고, 내부 노드의 수가 전체 노드 수의 작은 부분을 차지하기 때문이다. 그러나 최악의 경우, 특히 객체들이 서로 멀리 떨어져 있어 빈 공간을 분할하기 위해 많은 내부 노드가 생성될 경우, 공간 복잡도는 O(NlogN) 또는 그 이상으로 증가할 수 있다. 선형 옥트리의 경우 포인터 오버헤드가 없으므로 공간 효율성이 더 높다.32

4.2 최선, 평균, 최악의 경우 성능에 영향을 미치는 요인

옥트리의 점근적 복잡도는 평균적인 경우를 가정한 것이며, 실제 성능은 여러 요인에 의해 크게 달라질 수 있다.

• 데이터의 공간적 분포: 옥트리 성능에 가장 큰 영향을 미치는 요인은 데이터의 분포이다.9 데이터가 처리하려는 공간 전체에 걸쳐 비교적 균일하게 분포되어 있을 때, 옥트리는 균형 잡힌 구조를 형성하며 O(\log N)의 이상적인 성능을 보인다. 이것이 **평균적인 경우(average case)**이다.
• 최악의 경우 (Worst Case): 반면, 데이터가 극단적으로 불균일하게 분포할 때 성능은 급격히 저하된다. 예를 들어, N개의 모든 객체가 3차원 공간상의 한 직선 위에 매우 가깝게 위치하는 경우를 생각해보자. 이 객체들을 분리하기 위해 옥트리는 해당 직선을 포함하는 아주 작은 영역으로 계속해서 파고들어가야 하며, 이는 한쪽으로만 길게 늘어진 불균형 트리(unbalanced tree)를 생성한다. 이 경우 트리의 깊이는 N에 비례하게 되어, 탐색, 삽입, 삭제 연산의 시간 복잡도는 선형 탐색과 같은 O(N)으로 저하된다.38 또 다른 최악의 시나리오는 서로 매우 가깝게 뭉쳐 있는 여러 개의 작은 클러스터들이 서로는 아주 멀리 떨어져 있는 경우이다. 이 클러스터들을 분리하기 위해 그 사이의 방대한 빈 공간을 불필요하게 여러 번 분할해야 하므로, 트리의 깊이가 객체의 수와 무관하게 매우 깊어질 수 있다.9
• 객체의 크기와 형태: 포인트 데이터가 아닌 부피를 가진 객체를 다룰 때, 객체의 크기가 노드의 크기에 비해 매우 크면 해당 객체는 트리의 상위 레벨에 머무르거나 여러 리프 노드에 중복으로 저장될 수 있다. 이는 공간 분할의 효율을 떨어뜨리고 쿼리 시 더 많은 노드를 방문하게 만들어 성능을 저하시키는 요인이 된다.42

4.3 캐시 효율성 및 데이터 지역성이 실제 성능에 미치는 영향

이론적인 점근적 복잡도 분석만으로는 실제 하드웨어에서 나타나는 성능을 완벽하게 예측할 수 없다. 현대 CPU 아키텍처에서 메모리 접근 속도는 연산 속도에 비해 매우 느리기 때문에, 캐시 효율성(cache efficiency)과 데이터 지역성(data locality)이 실제 성능에 결정적인 영향을 미친다.

전통적인 포인터 기반 옥트리 구현은 이 측면에서 취약점을 보인다. 재귀적 트리 순회는 메모리 상에서 서로 멀리 떨어진 주소에 위치한 노드들을 무작위로 점프하며 접근하는 경향이 있다.27 이러한 불규칙한 메모리 접근 패턴은 CPU 캐시의 예측을 어렵게 하고 캐시 미스(cache miss)를 빈번하게 유발한다. 캐시 미스가 발생하면 CPU는 훨씬 느린 주 메모리(RAM)에서 데이터를 가져올 때까지 기다려야 하므로, 전체적인 실행 속도가 크게 저하된다.30

이 때문에 객체의 수가 수백, 수천 개 정도로 많지 않은 경우에는, 이론적으로 비효율적인 O(N^2)의 단순 배열 순차 탐색이 캐시 비효율적인 O(NlogN) 옥트리 순회보다 오히려 더 빠른 역설적인 현상이 발생할 수 있다.30 이는 CPU의 프리페칭(prefetching) 기능이 배열과 같은 연속된 메모리 구조에 대한 순차 접근을 매우 효율적으로 처리하기 때문이다.

이러한 문제를 해결하기 위해 선형 옥트리나, 노드들을 메모리 풀(memory pool) 또는 블록 단위로 할당하여 연속된 메모리 공간에 배치하는 캐시 친화적(cache-friendly) 구현 방식이 고안되었다. 이러한 방식들은 데이터 지역성을 향상시켜 캐시 히트율을 높이고, 특히 수백만 개 이상의 대규모 데이터셋을 처리할 때 포인터 기반 구현에 비해 상당한 실질적 성능 향상을 가져온다.29

4.4 표 IV-1: 옥트리 연산의 시간 복잡도

다음 표는 옥트리의 주요 연산에 대한 이론적 시간 복잡도를 요약한 것이다. 이 표는 데이터 분포가 성능에 미치는 영향을 명확히 보여주며, 특정 사용 사례에서 옥트리의 성능을 예측하고 다른 자료구조와 비교하는 데 유용한 기준을 제공한다.

5. 다른 공간 분할 자료구조와의 비교 분석

옥트리는 3차원 공간을 분할하는 여러 자료구조 중 하나이며, 각 자료구조는 고유한 분할 전략과 특성을 가지고 있어 특정 응용 분야에 더 적합할 수 있다. 옥트리의 상대적인 장단점을 이해하기 위해 k-d 트리, 경계 볼륨 계층(BVH), 그리고 균등 그리드와 비교 분석한다.

5.1 옥트리 vs. k-d 트리

• 분할 전략의 차이: 두 자료구조의 가장 근본적인 차이는 공간을 분할하는 방식에 있다. 옥트리는 각 노드에서 공간을 X, Y, Z 세 축에 평행한 평면으로 동시에 분할하여 8개의 정육면체(또는 직육면체) 형태의 자식 노드를 생성하는 8진 트리(8-ary tree) 구조이다.2 반면, k-d 트리는 트리의 각 레벨(깊이)마다

하나의 축을 선택하여 그 축에 수직인 평면으로 공간을 둘로 나누는 이진 트리(binary tree)이다.2 분할 축은 보통 X, Y, Z 순서로 순환하거나(예: 루트는 X, 다음 레벨은 Y, 그 다음은 Z, 다시 X…), 또는 해당 노드에 포함된 데이터가 가장 넓게 분포된 축을 동적으로 선택하는 방식을 사용한다.53

• 셀(Cell) 형태와 데이터 적응성: 옥트리의 분할은 항상 공간의 중심에서 이루어지므로, 생성되는 모든 셀은 부모와 동일한 종횡비를 갖는 정육면체 형태를 유지한다. 이는 셀의 모양이 매우 규칙적이고 예측 가능함을 의미한다.50 반면, k-d 트리는 종종 데이터 포인트들의 중간값(median)을 기준으로 분할 평면의 위치를 결정한다. 이로 인해 k-d 트리는 데이터의 분포에 더 잘 적응(adaptive)할 수 있지만, 생성되는 셀의 형태가 길고 납작한 비등방성(anisotropic)을 띠게 될 수 있다.50

• 성능 및 사용 사례: 데이터 분포에 더 잘 적응하는 k-d 트리의 특성은 희소하거나 불균일한 데이터셋에서 최근접 이웃 탐색(NNS)과 같은 쿼리에 대해 더 나은 성능을 보이는 경향이 있다.50 그러나 특정 반경 내의 모든 점을 찾는 반경 탐색(radius search)에서는 규칙적인 셀 모양을 가진 옥트리가 탐색해야 할 인접 셀을 계산하기 용이하여 더 효율적인 성능을 보이는 경우가 많다.47 또한, k-d 트리는 데이터의 삽입 및 삭제가 빈번할 경우 트리의 균형을 유지하기 위한 재조정(rebalancing) 과정이 복잡하고 비용이 많이 들 수 있다. 반면, 옥트리는 데이터 분포에 따라 불균형해질 수는 있지만 별도의 재조정 과정이 필요 없다는 점에서 동적 환경에 더 단순하게 적용될 수 있다.50

5.2 옥트리 vs. 경계 볼륨 계층(BVH)

• 근본적인 패러다임의 차이: 옥트리와 BVH는 종종 혼용되지만, 근본적으로 다른 패러다임에 속한다. 옥트리는 공간 분할(space partitioning) 방식이다. 즉, 공간 자체를 먼저 규칙적으로 나누고, 그 분할된 공간(셀)에 객체들을 할당하는 ‘top-down’ 접근법이다.55 반면, BVH는

객체 분할(object partitioning) 방식이다. 이는 객체들의 집합을 기준으로 시작하여, 가까이 있는 객체들을 그룹으로 묶고, 그 그룹 전체를 감싸는 최소한의 경계 볼륨(bounding volume)을 계산한다. 이 과정을 재귀적으로 반복하여 경계 볼륨들의 계층 구조를 만드는 ‘bottom-up’ 또는 ‘top-down’ 접근법이다.41

• 객체 소속 및 경계 볼륨의 정밀도: 이 패러다임의 차이는 중요한 결과로 이어진다. 옥트리에서는 하나의 객체가 여러 셀의 경계에 걸칠 경우, 여러 셀에 중복으로 포함될 수 있다.55 하지만 BVH에서는 각 객체(또는 삼각형과 같은 기본 프리미티브)가 오직 하나의 리프 노드에만 속하게 된다.59 또한, 옥트리 노드의 경계는 항상 축에 정렬된 정육면체 형태를 갖는 반면, BVH 노드의 경계 볼륨은 객체들의 분포에 최대한 밀착(tight-fitting)되도록 생성될 수 있다. AABB뿐만 아니라 방향성 있는 경계 상자(OBB), 구(sphere) 등 다양한 형태의 경계 볼륨을 사용할 수 있어, 불필요한 빈 공간을 최소화할 수 있다.57

• 성능 및 사용 사례: 경계 볼륨이 객체에 더 밀착된다는 특성 때문에, BVH는 특히 실시간 광선 추적(ray tracing)과 같이 정밀한 가지치기가 성능에 결정적인 영향을 미치는 응용 분야에서 옥트리보다 우수한 성능을 보이는 경우가 많다.12 광선이 경계 볼륨과 교차하지 않으면 그 안의 모든 객체를 안전하게 건너뛸 수 있는데, 이 경계 볼륨이 작을수록 광선이 빗나갈 확률이 높아지기 때문이다. 반면, 옥트리는 구조가 더 규칙적이고 구축이 상대적으로 간단하며, 복셀 기반의 렌더링이나 균일한 포인트 클라우드 데이터 처리 등에서 강점을 보인다.

5.3 옥트리 vs. 균등 그리드/공간 해싱

• 적응성과 메모리 효율성: 균등 그리드(Uniform Grid)는 전체 공간을 고정된 크기의 셀(복셀)들로 격자처럼 나누는 가장 단순한 공간 분할 방식이다.11 이 방식은 구현이 매우 간단하고 특정 위치의 셀을 찾는 데 O(1)의 시간이 걸리는 장점이 있다. 그러나 데이터가 없는 방대한 빈 공간에도 셀을 위한 메모리를 할당해야 하므로, 데이터가 희소하게 분포하는 경우 극심한 메모리 낭비를 초래한다.5 옥트리는 데이터가 존재하는 영역만 선택적으로 세분화하는

적응형(adaptive) 구조이므로, 이러한 상황에서 메모리 효율성이 월등히 뛰어나다.9 공간 해싱(Spatial Hashing)은 무한하거나 매우 넓은 공간을 유한한 크기의 해시 테이블로 매핑하여 균등 그리드의 메모리 문제를 해결하는 기법이다.

• 탐색 성능과 데이터 분포: 데이터가 공간에 매우 균일하게 분포되어 있다면, 균등 그리드나 공간 해싱은 이웃 셀을 찾는 데 거의 상수 시간(O(1))이 걸리므로 매우 빠른 성능을 보인다.53 하지만 데이터가 특정 지역에 극도로 밀집된 ‘클러스터링’ 현상이 발생하면, 공간 해싱에서는 하나의 해시 버킷에 너무 많은 객체가 몰려 성능이 선형 탐색 수준으로 저하될 수 있다(해시 충돌).53 옥트리는 계층적 구조를 통해 이러한 밀집 지역을 더 작은 셀로 자동 분할하여 부하를 분산시키므로, 데이터 밀도가 불균일한 환경에 더 강건(robust)하다.

5.4 표 V-1: 공간 분할 자료구조 비교

다음 표는 3차원 공간 데이터를 처리하는 데 사용되는 주요 자료구조들의 핵심적인 특징과 장단점을 요약하여 비교한다. 이는 특정 응용 프로그램의 요구사항에 가장 적합한 자료구조를 선택하는 데 실용적인 가이드라인을 제공한다.

6. 핵심 응용 분야

옥트리는 그 효율적인 공간 분할 능력 덕분에 다양한 컴퓨팅 분야에서 핵심적인 자료구조로 활용되고 있다. 옥트리는 단순히 점을 저장하는 구조를 넘어, 각 응용 분야의 특정 문제를 해결하기 위한 ‘메타 구조’ 또는 ’프레임워크’로서 기능한다. 즉, 옥트리의 기본 ‘재귀적 8분할’ 구조는 동일하게 유지되지만, 각 노드에 어떤 종류의 데이터를 저장하고 어떻게 순회하는지에 따라 특정 도메인에 최적화된 솔루션으로 변모한다.

6.1 컴퓨터 그래픽스

컴퓨터 그래픽스는 옥트리가 탄생하고 가장 활발하게 활용되어 온 분야이다. 3차원 가상 세계의 복잡성을 관리하고 실시간으로 렌더링하기 위한 다양한 문제 해결에 옥트리가 사용된다.

• 실시간 충돌 감지 (Real-time Collision Detection): 수천 개의 객체가 존재하는 복잡한 3D 장면에서 모든 객체 쌍의 충돌 여부를 검사하는 것은 O(N^2)의 계산량을 요구하여 실시간 처리가 불가능하다.8 옥트리는 이 문제에 대한 효율적인 해결책을 제공한다. 먼저, 모든 객체를 옥트리에 삽입하여 공간적으로 정렬한다. 그 후, 각 객체에 대해 자신이 속한 노드 및 인접 노드에 있는 다른 객체들과만 충돌 검사를 수행한다. 이는 물리적으로 멀리 떨어져 있어 충돌 가능성이 없는 방대한 수의 객체 쌍을 검사 대상에서 제외하는 ‘후보군 필터링’ 역할을 한다. 이 넓은 단계(broad phase)에서의 효율적인 필터링 덕분에 전체 충돌 감지 연산량을

O(NlogN) 수준으로 크게 줄일 수 있다.4

• 시야 절두체 컬링 (View Frustum Culling): 3D 렌더링 파이프라인의 효율을 높이기 위한 핵심 최적화 기법 중 하나이다. 카메라의 시야 범위는 수학적으로 절두체(frustum)라는 6개의 평면으로 둘러싸인 공간으로 정의된다.64 이 절두체 내부에 있는 객체만이 화면에 보이므로, 외부에 있는 객체들은 렌더링할 필요가 없다. 옥트리는 이 ’가시성 계층’을 효과적으로 관리한다. 렌더링 매 프레임마다 옥트리를 루트 노드부터 재귀적으로 순회하며, 각 노드의 경계 상자가 절두체와 교차하는지 검사한다. 만약 노드의 경계 상자가 절두체 외부에 완전히 벗어나 있다면, 해당 노드에 포함된 모든 하위 객체들은 더 이상 검사할 필요 없이 한 번에 렌더링 대상에서 제외(cull)된다. 이를 통해 GPU로 전송되는 데이터의 양을 크게 줄여 렌더링 성능을 향상시킨다.6

• 광선 추적 가속화 (Ray Tracing Acceleration): 사실적인 이미지를 생성하는 광선 추적 기법은 화면의 각 픽셀에서 가상의 광선을 쏘아 장면에 있는 객체와의 교차점을 찾는 과정이다. 장면이 복잡할수록 광선 하나가 수많은 객체와 교차 검사를 수행해야 하므로 계산 비용이 매우 높다. 옥트리는 이 과정을 가속화하기 위한 공간 분할 구조로 사용된다. 광선이 옥트리의 루트 노드와 교차하면, 광선이 통과하는 자식 노드들을 계산하여 그 경로를 따라 트리를 순회한다. 이 과정에서 광선이 통과하지 않는 노드들은 모두 건너뛰고, 광선이 도달한 리프 노드에 포함된 소수의 객체들에 대해서만 정밀한 광선-객체 교차 검사를 수행한다. 이는 불필요한 교차 검사 횟수를 획기적으로 줄여 렌더링 시간을 단축시킨다.65

• 색상 양자화 (Color Quantization): 24비트 트루컬러 이미지에 포함된 수백만 개의 고유한 색상을 256개와 같이 제한된 수의 대표 색상으로 줄여 이미지 파일 크기를 압축하는 기술이다. 옥트리 기반 색상 양자화 알고리즘은 각 픽셀의 RGB 값을 3차원 색상 공간 상의 한 점으로 간주한다.2 이 점들을 옥트리에 삽입하면, 색상 공간에서 유사한 색상들이 같은 리프 노드에 그룹화된다. 트리의 깊이를 제한하여 생성되는 리프 노드의 수를 제어할 수 있으며(예: 최대 256개), 각 리프 노드에 속한 모든 색상들의 평균값을 계산하여 최종 컬러 팔레트의 대표 색상으로 사용한다. 이 방법은 메모리 효율성이 높고 양질의 결과를 생성한다.2

6.2 3D 포인트 클라우드 처리

LiDAR 스캐너나 사진 측량 기술로 생성되는 포인트 클라우드는 수억 개에서 수십억 개에 이르는 점들의 집합으로, 원시 데이터 자체로는 다루기가 매우 어렵다. 옥트리는 이러한 대규모 포인트 클라우드를 효율적으로 관리하고 분석하기 위한 핵심 자료구조이다.

• 저장, 인덱싱, 쿼리: 옥트리는 포인트 클라우드 데이터를 위한 자연스러운 공간 인덱싱 구조를 제공한다. 각 점을 옥트리에 삽입하면, 데이터는 공간적 위치에 따라 계층적으로 정리된다. 이를 통해 특정 3차원 영역 내에 존재하는 모든 점을 빠르게 검색하거나(범위 쿼리), 특정 점에서 가장 가까운 이웃 점들을 효율적으로 찾는(NNS) 작업이 가능해진다.22 이는 객체 인식, 표면 재구성, 변화 탐지 등 다양한 후처리 작업의 기반이 된다.
• 복셀화 및 다중 해상도 표현 (Voxelization and Multi-resolution Representation): 포인트 클라우드를 옥트리에 삽입하는 과정은 자연스럽게 데이터를 복셀화(voxelization)하는 효과를 낳는다. 각 리프 노드는 하나의 복셀에 해당하며, 그 안에 포함된 점들의 평균 색상이나 밀도 등의 속성을 저장할 수 있다.22 옥트리의 계층적 특성은 다중 해상도(Level of Detail, LOD) 표현을 손쉽게 구현할 수 있게 한다. 트리의 상위 레벨로 갈수록 더 큰 복셀로 데이터를 뭉뚱그려 표현하므로, 전체적인 구조를 빠르게 파악하거나 렌더링할 수 있고, 필요에 따라 하위 레벨로 내려가 더 상세한 정보를 얻을 수 있다.72

6.3 로보틱스 및 SLAM (동시적 위치 추정 및 지도 작성)

자율 주행 로봇이나 드론이 미지의 환경을 탐색하고 작업을 수행하기 위해서는 자신의 위치를 파악하고 주변 환경 지도를 동시에 생성하는 SLAM 기술이 필수적이다. 옥트리는 이 과정에서 환경을 표현하는 표준적인 방식으로 널리 사용된다.

• 환경 지도 구축 (Environment Mapping): 로봇의 센서(LiDAR, 깊이 카메라 등)로부터 수집된 3차원 측정값은 옥트리 기반의 맵, 대표적으로 ’OctoMap’에 통합된다.75 OctoMap에서 각 옥트리 노드(복셀)는 단순히 비어 있거나 차 있는 상태(binary)가 아니라, 해당 공간이 장애물에 의해 점유될 확률(occupancy probability) 값을 저장한다.76 센서 데이터가 들어올 때마다 베이즈 필터링(Bayes filtering)을 통해 이 확률값이 갱신된다. 이를 통해 점유된 공간, 비어있는 공간, 아직 관측되지 않은 미지의 공간을 명확히 구분하는 3차원 확률적 점유 격자 지도(probabilistic occupancy grid map)를 생성할 수 있으며, 이는 로봇의 안전한 경로 계획 및 장애물 회피에 결정적인 정보를 제공한다.16
• SLAM 가속화: SLAM 과정에서 로봇의 위치를 추정하기 위해서는 새로 들어온 센서 데이터와 이전에 구축된 지도 데이터 간의 정합(registration)이 필요하다. 옥트리는 이 과정에서 새로 관측된 점들과 지도 상의 기존 점들 사이의 대응점(correspondence)을 빠르게 찾는 데 사용된다. 효율적인 최근접 이웃 탐색을 통해 데이터 연관(data association) 문제를 신속하게 해결함으로써, 로봇의 자세(pose)를 실시간으로 최적화하고 지도를 일관성 있게 갱신할 수 있다.47

6.4 지리 정보 시스템(GIS) 및 물리 시뮬레이션

• 지리 정보 시스템 (GIS): 옥트리는 도시 전체의 3D 건물 모델, 광범위한 지역의 디지털 지형 모델(DTM)과 같이 방대한 규모의 3차원 지리 공간 데이터를 효율적으로 저장, 관리, 시각화하고 분석하는 데 활용된다. 사용자가 특정 지역을 확대하면 옥트리의 하위 레벨로 내려가 상세 정보를 로드하고, 축소하면 상위 레벨의 개략적인 정보를 보여주는 식으로 다중 해상도 시각화를 구현할 수 있다.4
• 물리 시뮬레이션 및 전산 유체 역학 (CFD): 복잡한 형상(예: 자동차, 항공기) 주위의 공기 흐름이나 열 전달을 시뮬레이션하기 위해서는 해당 공간을 작은 계산 격자(mesh)로 나누어야 한다. 옥트리 기반 메시 생성 기법은 이 과정을 자동화하고 가속화하는 데 매우 효과적이다. 이 기법은 시뮬레이션 공간을 옥트리로 분할한 후, 객체의 표면과 같이 물리적 변화가 급격할 것으로 예상되는 영역의 셀은 잘게 나누고, 변화가 완만한 영역의 셀은 크게 유지하는 적응형 메시(adaptive mesh)를 생성한다. 이는 계산의 정확도를 유지하면서도 전체 격자의 수를 줄여 시뮬레이션 시간을 단축시키는 데 기여한다.82

7. 고급 옥트리 기법 및 최신 연구 동향

옥트리는 40년 이상의 역사를 가진 고전적인 자료구조이지만, 하드웨어의 발전과 데이터 규모의 폭증이라는 시대적 요구에 부응하며 끊임없이 진화하고 있다. 현대의 옥트리 연구는 단순한 알고리즘 개선을 넘어, 병렬 컴퓨팅, 대규모 데이터 처리, 인공지능과의 융합 등 새로운 컴퓨팅 패러다임에 최적화된 형태로 발전하고 있다.

7.1 주요 변종 옥트리

전통적인 옥트리의 한계를 극복하기 위해 다양한 변종들이 제안되었다.

• 느슨한 옥트리 (Loose Octrees): 이 기법은 동적 객체 관리의 어려움, 특히 객체가 노드 경계를 자주 넘나들 때 발생하는 빈번한 업데이트 비용 문제를 해결하기 위해 고안되었다. 느슨한 옥트리는 각 노드의 경계 상자를 실제 기하학적 범위보다 일정 비율(k-factor, 보통 1.5에서 2.0 사이)만큼 인위적으로 확장한다.41 이렇게 하면 객체가 작은 움직임으로는 확장된 경계(loose bound)를 벗어나지 않게 되어, 트리 상에서 노드를 변경해야 하는 빈도가 크게 줄어든다. 또한, 부피가 큰 객체도 경계에 걸치지 않고 하나의 리프 노드에 완전히 포함될 가능성이 높아져 부모 노드에 객체가 쌓이는 문제를 완화한다. 이로 인해 객체의 삽입 및 삭제 연산이 훨씬 빨라지지만, 노드 간 경계가 서로 겹치게 되므로 공간 분할의 정밀도가 다소 떨어져 쿼리 시 더 많은 노드를 검사해야 할 수 있다는 단점이 있다.41
• 희소 복셀 옥트리 (Sparse Voxel Octree, SVO): SVO는 3차원 장면을 복셀(voxel)로 표현하되, 데이터가 없는 방대한 빈 공간에 해당하는 노드는 아예 생성하거나 저장하지 않음으로써 메모리 사용량을 극적으로 절약하는 기법이다.84 특히 객체의 표면만을 복셀화하여 저장할 때 그 효과가 극대화된다. SVO는 단순히 데이터를 압축하는 것을 넘어, 계층 구조를 활용한 효율적인 광선 순회(ray traversal) 알고리즘과 결합하여 대규모 복셀 장면의 실시간 렌더링을 가능하게 한다. 이는 ’복셀 기반 전역 조명(Voxel-Based Global Illumination, VXGI)’과 같은 고급 렌더링 기술의 핵심 기반이 된다.12 SVO의 구현은 데이터 압축률과 순회 속도를 높이기 위해 포인터 대신 비트 마스크와 상대 주소 지정 방식을 사용하는 등 고도로 최적화된 메모리 레이아웃을 특징으로 한다.85

7.2 최적화 기법

현대 컴퓨팅 환경의 특성을 최대한 활용하기 위한 다양한 최적화 기법이 연구되고 있다.

• GPU 병렬 처리를 통한 가속: 옥트리의 구축 및 순회 알고리즘은 재귀적인 특성상 독립적으로 처리할 수 있는 작업 단위가 많아 병렬화에 매우 적합하다. CUDA나 OpenCL과 같은 GPGPU(General-Purpose computing on Graphics Processing Units) 기술을 활용하여, 수천 개의 코어를 가진 GPU에서 옥트리 연산을 동시에 처리함으로써 성능을 수십 배에서 수백 배까지 향상시킬 수 있다.88 특히 데이터가 메모리에 연속적으로 배치되는 선형 옥트리는 GPU의 SIMD(Single Instruction, Multiple Data) 아키텍처에 매우 친화적이어서 병렬 처리에 큰 이점을 가진다.37
• 캐시 친화적 메모리 레이아웃 (Cache-Friendly Memory Layout): 앞서 언급했듯이, 전통적인 포인터 기반 구현은 캐시 비효율성을 야기한다. 이를 개선하기 위해 노드들을 하나의 거대한 배열이나 메모리 풀에 연속적으로 할당하고, 포인터 대신 배열 인덱스를 사용하여 자식 노드를 참조하는 방식이 널리 사용된다. 이는 데이터 지역성(data locality)을 높여 캐시 히트율을 극대화하고, 메모리 접근으로 인한 병목 현상을 완화하여 실제 실행 속도를 크게 향상시킨다.29
• 분산 및 병렬 처리 (Out-of-Core and Distributed Processing): 단일 컴퓨터의 주 메모리 용량을 초과하는 수십억, 수조 단위의 초거대 포인트 클라우드 데이터셋을 처리하기 위한 ‘Out-of-Core’ 기법이 활발히 연구되고 있다. 이 접근법은 전체 데이터를 디스크에 저장한 채, 먼저 데이터를 공간적으로 관련된 여러 개의 작은 청크(chunk)로 분할한다.74 그 후, 각 청크를 메모리에 개별적으로 로드하여 병렬적으로 로컬 옥트리를 구축한다. 마지막으로, 이렇게 생성된 여러 개의 로컬 옥트리들을 병합하여 최종적인 전역 옥트리를 완성한다. 이 과정은 대규모 클러스터나 클라우드 컴퓨팅 환경에서 수행될 수 있으며, 사실상 무한한 크기의 데이터셋을 처리할 수 있는 확장성을 제공한다.37

7.3 최신 연구 동향

옥트리는 최신 기술 트렌드와 결합하며 새로운 가능성을 열어가고 있다.

• 동적 및 증분 업데이트 (Dynamic and Incremental Updates): 실시간 SLAM, 증강 현실(AR), 동적 물리 시뮬레이션과 같이 환경이 지속적으로 변화하는 응용 분야에서는 맵이나 데이터 구조를 빠르고 효율적으로 갱신하는 능력이 매우 중요하다. 이를 위해 기존의 정적 옥트리를 개선하여, 새로운 데이터의 점진적 삽입(incremental insertion), 기존 데이터의 삭제, 특정 영역의 일괄 삭제 등을 고속으로 처리하는 동적 옥트리 구조에 대한 연구가 활발히 진행 중이다. 예를 들어, i-Octree는 이러한 동적 연산에 최적화되어 기존 방식보다 수십 배 빠른 업데이트 성능을 보여준다.47
• 신경망 및 딥러닝과의 결합 (Integration with Neural Networks): 옥트리는 3차원 데이터에 대한 딥러닝 모델의 효율성과 성능을 향상시키는 데 중요한 역할을 한다. 3D 형상이나 포인트 클라우드를 직접 처리하는 신경망은 종종 엄청난 메모리와 계산량을 요구한다. 옥트리는 이러한 데이터의 희소성을 활용하여, 데이터가 존재하는 영역에 대해서만 계산을 집중하도록 신경망의 연산을 안내할 수 있다. 예를 들어, 옥트리 기반의 계층적 샘플링 기법을 사용하여 과학 데이터의 초해상도(super-resolution) 복원 모델의 학습을 가속화하고 수렴 성능을 개선하는 연구가 있다.92 또한, 3차원 장면의 특징을 옥트리 구조에 인코딩하여 효율적인 표현을 학습하는 데에도 활용된다.93
• 신경 렌더링과의 통합 (Integration with Neural Rendering): NeRF(Neural Radiance Fields)나 3D 가우시안 스플래팅(3D Gaussian Splatting)과 같은 최신 신경 렌더링 기술은 전례 없는 품질의 3D 장면을 생성하지만, 렌더링 속도가 느리다는 단점이 있다. 옥트리는 이러한 기술의 렌더링 속도를 가속화하는 데 핵심적인 역할을 한다. 옥트리를 사용하여 렌더링 광선이 통과하는 빈 공간을 빠르게 건너뛰거나, 장면의 기하학적 정보를 계층적으로 인코딩하여 신경망의 쿼리 횟수를 줄이는 방식이다. 최근에는 옥트리 기반의 암시적 표면 표현(SDF)과 3D 가우시안을 결합하여 렌더링 품질과 속도를 모두 향상시키는 연구도 발표되었다.94
• 자동화된 특징 공학 (Automated Feature Engineering): 옥트리의 계층적 분할 아이디어는 3D 공간을 넘어 다른 분야로 확장되고 있다. 최근에는 대형 언어 모델(LLM)의 추론 능력을 활용하여 테이블 형식 데이터(tabular data)에 대한 최적의 특징(feature)을 자동으로 생성하는 프레임워크에 ’OCTree’라는 이름이 붙여지기도 했다. 이는 결정 트리(Decision Tree)를 통해 얻은 분석 정보를 LLM에 피드백으로 제공하여 반복적으로 특징 생성 규칙을 개선하는 방식으로, 옥트리의 개념적 구조가 데이터 과학 분야의 문제 해결에 영감을 줄 수 있음을 보여준다.96

이러한 연구 동향들은 옥트리가 더 이상 단일 CPU 코어에서 순차적으로 실행되는 고전적인 자료구조가 아니라, 현대의 이기종(heterogeneous) 및 분산 컴퓨팅 환경에 최적화되고 인공지능과 융합되는 방향으로 끊임없이 진화하고 있음을 명확히 보여준다.

8. 결론: 옥트리의 현재와 미래

8.1 옥트리의 핵심 장단점 요약

옥트리는 3차원 공간 데이터를 효율적으로 관리하기 위한 강력하고 다재다능한 자료구조로서, 지난 수십 년간 컴퓨터 과학의 여러 분야에서 그 가치를 입증해왔다. 옥트리의 핵심적인 장점과 내재적인 단점을 요약하면 다음과 같다.

장점:

• 효율적인 공간 검색: 옥트리의 가장 큰 장점은 계층적 구조를 통해 탐색 공간을 기하급수적으로 줄일 수 있다는 점이다. 관련 없는 방대한 공간을 신속하게 배제(pruning)함으로써 점, 범위, 최근접 이웃 등 다양한 유형의 공간 쿼리를 매우 빠르게 수행할 수 있다.4
• 적응형 해상도 (Adaptive Resolution): 데이터의 밀도에 따라 공간을 적응적으로 분할하는 능력은 옥트리의 또 다른 핵심 강점이다. 데이터가 밀집된 영역은 세밀하게, 희소한 영역은 넓게 표현함으로써 불필요한 메모리 낭비를 최소화하고, 데이터의 본질적인 구조를 효율적으로 포착한다.9
• 개념적 단순성과 구현 용이성: 재귀적으로 공간을 8개로 나눈다는 기본 개념은 다른 복잡한 공간 분할 구조에 비해 상대적으로 직관적이고 이해하기 쉽다. 이로 인해 기본적인 기능 구현이 비교적 용이하다.41
• 확장성 및 병렬화: 옥트리의 규칙적인 분할 구조는 대규모 데이터셋 처리로의 확장이 용이하며, 각 노드나 서브트리에 대한 연산을 독립적으로 수행할 수 있어 병렬 처리에 매우 적합하다.4

단점:

• 데이터 분포에 대한 민감성: 옥트리의 성능은 데이터의 공간적 분포에 크게 의존한다. 데이터가 한쪽으로 심하게 치우치거나 특정 선/면에 집중될 경우, 트리가 깊고 불균형하게 생성되어 성능이 선형 탐색 수준으로 저하될 수 있다.38
• 메모리 오버헤드: 포인터 기반으로 구현할 경우, 각 내부 노드는 8개의 자식 포인터를 저장해야 하므로 상당한 메모리 오버헤드가 발생할 수 있다. 또한, 트리가 깊어지면 노드 자체의 수가 많아져 전체 메모리 사용량이 증가한다.4
• 경계 객체 처리의 복잡성: 점이 아닌 부피를 가진 객체가 노드의 경계에 걸칠 때, 이를 처리하는 방식(객체 분할, 중복 참조, 부모 노드 저장 등)은 구현을 복잡하게 만들고 성능에 직접적인 영향을 미치는 트레이드오프를 수반한다.9
• 형상 표현의 부정확성: 옥트리는 공간을 정육면체(또는 직육면체) 셀의 집합으로 근사한다. 이로 인해 곡면이나 복잡한 경계를 가진 객체의 형상을 완벽하게 표현하지 못하고, 계단 현상(aliasing)과 같은 근사 오차가 발생할 수 있다.99

8.2 문제에 따른 자료구조 선택 가이드라인

특정 문제에 가장 적합한 공간 분할 자료구조를 선택하는 것은 시스템 전체의 성능을 좌우하는 중요한 설계 결정이다. 다음은 옥트리와 다른 주요 자료구조들 사이에서 선택하기 위한 실용적인 가이드라인이다.

옥트리 사용이 적합한 경우:

• 3차원 공간 데이터가 비교적 균일하게 분포하거나, 복셀 기반의 표현이 자연스러운 문제에 매우 적합하다. (예: 의료 영상 데이터, 볼륨 렌더링, 3D 스캐닝으로 얻은 밀도 높은 포인트 클라우드).100
• 데이터의 동적인 변화가 적거나, 매 프레임 재구축하는 비용을 감수할 수 있는 정적 장면에 대한 빠른 쿼리가 더 중요한 경우. (단, i-Octree와 같은 최신 동적 옥트리 변종은 이 단점을 상당 부분 완화한다).50
• 구현의 단순성과 예측 가능한 규칙적인 셀 구조가 복잡한 데이터 적응성보다 우선시될 때.

다른 자료구조를 고려해야 할 경우:

• k-d 트리: 데이터가 매우 희소하고 불균일하게 분포하며, **최근접 이웃 탐색(NNS)**이 주된 연산일 때 k-d 트리는 데이터 분포에 더 잘 적응하므로 옥트리보다 나은 선택일 수 있다.50
• BVH (경계 볼륨 계층): 렌더링할 프리미티브(주로 삼각형)가 명확하게 정의되어 있고, 실시간 광선 추적과 같이 객체에 최대한 밀착되는 타이트한 경계 볼륨이 성능에 결정적인 영향을 미칠 때 BVH가 거의 항상 더 우수한 성능을 보인다.55
• 공간 해싱 / 균등 그리드: 수많은 객체들이 예측 불가능하게 계속 움직이는 고도로 동적인 환경에서 빠른 삽입/삭제가 가장 중요하고, 데이터 분포가 비교적 균일할 때 이들 구조가 제공하는 O(1)의 평균 삽입/삭제/탐색 성능이 유리할 수 있다.53

8.3 미래 발전 방향 및 전망

40년이 넘는 긴 역사에도 불구하고 옥트리는 사장되지 않고 오히려 현대 컴퓨팅의 발전에 발맞춰 끊임없이 진화하고 있는 살아있는 자료구조이다. 옥트리의 미래는 특히 인공지능 기술과의 깊은 융합에서 찾아볼 수 있다.

3차원 공간을 이해하고 생성하는 딥러닝 모델, 특히 신경 렌더링(Neural Rendering) 분야에서 옥트리는 강력한 공간적 사전 정보(spatial prior)를 제공하는 역할을 한다. 신경망이 비어있는 공간에 불필요한 연산을 낭비하지 않도록 안내하고, 장면의 구조를 계층적으로 인코딩하여 학습과 렌더링을 가속화하는 데 핵심적인 역할을 수행할 것이다.94 즉, 옥트리는 순수 기하학적 자료구조를 넘어, 3D-AI 모델을 위한 효율적인 ’백본(backbone)’으로 자리매김할 가능성이 높다.

또한, 하드웨어 기술의 발전은 옥트리의 진화를 계속해서 촉진할 것이다. GPU, TPU와 같은 병렬 처리 장치에 더욱 최적화된 새로운 옥트리 변종과 라이브러리들이 등장하여, 실시간 인터랙티브 물리 시뮬레이션, 도시 규모의 디지털 트윈, 자율 주행 자동차의 실시간 환경 인식 등에서 처리할 수 있는 데이터의 규모와 복잡성의 한계를 계속해서 확장해 나갈 것으로 전망된다. 옥트리는 과거의 유산이 아니라, 미래의 3차원 디지털 세계를 구축하는 데 있어 여전히 필수적인 구성 요소로 남을 것이다.

9. 참고 자료

1. en.wikipedia.org, https://en.wikipedia.org/wiki/Octree#:~:text=An%20octree%20is%20a%20tree,three%2Ddimensional%20analog%20of%20quadtrees.
2. Octree - Wikipedia, https://en.wikipedia.org/wiki/Octree
3. Octree | Insertion and Searching - GeeksforGeeks, https://www.geeksforgeeks.org/dsa/octree-insertion-and-searching/
4. Octrees: The Ultimate Spatial Data Structure - Number Analytics, https://www.numberanalytics.com/blog/octrees-ultimate-spatial-data-structure
5. Octree / PCL - adioshun, https://adioshun.gitbooks.io/pcl/content/Tutorial/Octree/
6. 4.2. How octree works - Castle Game Engine, https://castle-engine.io/vrml_engine_doc/output/xsl/html/section.how_octree_works.html
7. Octrees – Knowledge and References - Taylor & Francis, https://taylorandfrancis.com/knowledge/Engineering_and_technology/Computer_science/Octrees/
8. Introduction to Octrees - Wobbly Duck Studios, https://www.wobblyduckstudios.com/Octrees.php
9. Advanced Octrees 1: preliminaries, insertion strategies and maximum tree depth, https://geidav.wordpress.com/2014/07/18/advanced-octrees-1-preliminaries-insertion-strategies-and-max-tree-depth/
10. collision detection and oct trees : r/cpp_questions - Reddit, https://www.reddit.com/r/cpp_questions/comments/1b271t6/collision_detection_and_oct_trees/
11. Octrees for Efficient Spatial Analysis - Number Analytics, https://www.numberanalytics.com/blog/octrees-efficient-spatial-analysis
12. Why are oct trees so much more common than hash tables?, https://computergraphics.stackexchange.com/questions/8364/why-are-oct-trees-so-much-more-common-than-hash-tables
13. Geometric Modeling Using Octree Encoding - MIT Fab Lab, http://fab.cba.mit.edu/classes/S62.12/docs/Meagher_octree.pdf
14. The Octree Encoding Method for Efficient Solid Modeling. - DTIC, https://apps.dtic.mil/sti/tr/pdf/ADA132472.pdf
15. Mastering Octrees in Algorithm Design - Number Analytics, https://www.numberanalytics.com/blog/ultimate-guide-to-octree-in-algorithm-design
16. Mastering Octrees in Topological Robotics - Number Analytics, https://www.numberanalytics.com/blog/ultimate-guide-octrees-topological-robotics
17. Data Structure / Algorithm - 쿼드 트리 (Quadtree) 공간 분할 - joonyle99’s Blog, https://joonyle99.github.io/datastructure_algorithm/DataStructure_Algorithm-Quadtree/
18. ‘자 & 알/알고리즘’ 카테고리의 글 목록 (2 Page), https://hyo-ue4study.tistory.com/category/%EC%9E%90%20%26%20%EC%95%8C/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98?page=2
19. An interactive explanation of quadtrees. : r/programming - Reddit, https://www.reddit.com/r/programming/comments/25ivi5/an_interactive_explanation_of_quadtrees/
20. Name of the generalization of quadtree and octree? - Mathematics Stack Exchange, https://math.stackexchange.com/questions/644032/name-of-the-generalization-of-quadtree-and-octree
21. Octree-Node / 3DCollisions - gdbooks, https://gdbooks.gitbooks.io/3dcollisions/content/Chapter5/dynamic_objects.html
22. Octree - Open3D 0.17.0 documentation, https://www.open3d.org/docs/0.17.0/tutorial/geometry/octree.html
23. Octree - Open3D 0.13.0 documentation, https://www.open3d.org/docs/0.13.0/tutorial/geometry/octree.html
24. Octree, https://www.cg.tuwien.ac.at/studentwork/VisFoSe98/eder/octree.htm
25. Voxel Octree & Visualization - 기억 저장소 - 티스토리, https://nature77s.tistory.com/20
26. tutorials/OpenGL/Octree/Octree.cpp at master / gametutorials/tutorials - GitHub, https://github.com/gametutorials/tutorials/blob/master/OpenGL/Octree/Octree.cpp
27. Constructing an Octree Datastructure - MGhabboun’s Technical Blog, https://mghabboun.wordpress.com/2017/02/27/constructing-an-octree-datastructure/
28. 대용량 3차원 포인트 클라우드의 탐색을 위한 메모리 효율적인 옥트리의 설계 - Korea Science, https://koreascience.kr/article/JAKO201315463255209.pdf
29. Adaptive Fluid Simulation Using a Linear Octree Structure, https://www.cs.jhu.edu/~misha/ReadingSeminar/Papers/Flynn18.pdf
30. octree-based frustum culling slower than naive? : r/GraphicsProgramming - Reddit, https://www.reddit.com/r/GraphicsProgramming/comments/1ia2rhd/octreebased_frustum_culling_slower_than_naive/
31. Statistical optimization of octree searches - Thomas Lewiner, http://thomas.lewiner.org/pdfs/octree_cgf.pdf
32. www.sci.utah.edu, https://www.sci.utah.edu/~knolla/octsurvey.pdf
33. An interactive explanation of quadtrees (2014) - Hacker News, https://news.ycombinator.com/item?id=34786075
34. An Octree-Based Spatial Index for Space-Based Space Surveillance Coverage Volume Computation, https://arc.aiaa.org/doi/pdfplus/10.2514/6.2024-1675
35. A Fast Algorithm to Display Octrees - CSE, IIT Bombay, https://www.cse.iitb.ac.in/~sharat/icvgip.org/icvgip00/G-51.pdf
36. 선형 Octree에 의한 CT 영상의 3차원 재구성 및 표현, https://koreascience.kr/article/JAKO198915875835751.pdf
37. Cornerstone: Octree Construction Algorithms for Scalable Particle Simulations - arXiv, https://arxiv.org/pdf/2307.06345
38. Octree에 대해 설명해주세요. - velog, https://velog.io/@tmdwns8840/Octree%EC%97%90-%EB%8C%80%ED%95%B4-%EC%84%A4%EB%AA%85%ED%95%B4%EC%A3%BC%EC%84%B8%EC%9A%94
39. What is the logic to recursively subdivide an octree? - Stack Overflow, https://stackoverflow.com/questions/48720767/what-is-the-logic-to-recursively-subdivide-an-octree
40. Lodestar - Tech - Octree Algorithms, https://www.cg.tuwien.ac.at/research/vr/lodestar/tech/octree/
41. What are common benefits and uses of Octrees? : r/GraphicsProgramming - Reddit, https://www.reddit.com/r/GraphicsProgramming/comments/10mf504/what_are_common_benefits_and_uses_of_octrees/
42. Loose octrees for frustum culling - Need some advice - Stack Overflow, https://stackoverflow.com/questions/5297721/loose-octrees-for-frustum-culling-need-some-advice
43. Using Octrees and A* for Efficient Pathfinding - YouTube, https://www.youtube.com/watch?v=gNmPmWR2vV4&pp=0gcJCfwAo7VqN5tD
44. 포인트 탐색과 배경제거 (60%) - Tutorial, https://pcl.gitbook.io/tutorial/part-2/part02-chapter02
45. Octree-kdTree / 3D_People_Detection - adioshun, https://adioshun.gitbooks.io/3d_people_detection/content/ebook/part02/part02-chapter02.html
46. Subdividing an octree branch is easy, as the old value is simply replaced by the index to the new data, but how can I handle the gaps in the data created by merging an octree branch? The 8 or more elements will suddenly become just 1 and there will be gaps in the data : r/VoxelGameDev - Reddit, https://www.reddit.com/r/VoxelGameDev/comments/st8vjp/subdividing_an_octree_branch_is_easy_as_the_old/
47. A Fast, Lightweight, and Dynamic Octree for Proximity Search - arXiv, https://arxiv.org/html/2309.08315v2
48. Question on complexity of Barnes-Hut algorithm - Software Engineering Stack Exchange, https://softwareengineering.stackexchange.com/questions/382312/question-on-complexity-of-barnes-hut-algorithm
49. Mastering Octrees in Computational Geometry - Number Analytics, https://www.numberanalytics.com/blog/ultimate-guide-octrees-computational-geometry
50. Why would one ever use an Octree over a KD-tree?, https://cstheory.stackexchange.com/questions/8470/why-would-one-ever-use-an-octree-over-a-kd-tree
51. Spatial data structures: Octrees, BSP, and k-d trees / Tim Henning | Observable, https://observablehq.com/@2talltim/spatial-data-structures-octrees-bsp-and-k-d-trees
52. kd-트리 - 코딩연습블로그 - 티스토리, https://coding6467.tistory.com/13
53. Why specifically are k-d trees preferred in ray tracing and octrees in collision? - Reddit, https://www.reddit.com/r/gameenginedevs/comments/1789f54/why_specifically_are_kd_trees_preferred_in_ray/
54. kd-tree vs octree for 3d radius search - Stack Overflow, https://stackoverflow.com/questions/17998103/kd-tree-vs-octree-for-3d-radius-search
55. Difference between BVH and Octree/K-d trees - Computer Graphics Stack Exchange, https://computergraphics.stackexchange.com/questions/7828/difference-between-bvh-and-octree-k-d-trees
56. Ray Tracing From Scratch: Grid & BVH Comparison | by Muhammed Can Erbudak - Medium, https://medium.com/@muhammedcan.erbudak/ray-tracing-from-scratch-grid-bvh-comparison-faa1c27f2832
57. Bounding volume hierarchy - Wikipedia, https://en.wikipedia.org/wiki/Bounding_volume_hierarchy
58. Bounding Volume Hierarchy: BVH (part 2) - Introduction to Acceleration Structures, https://www.scratchapixel.com/lessons/3d-basic-rendering/introduction-acceleration-structure/bounding-volume-hierarchy-BVH-part2.html
59. Lecture-19-BVH and Octrees, https://courses.grainger.illinois.edu/cs419/sp2017/Lecture-19-BVH%20and%20Octrees.pdf
60. When to use Binary Space Partitioning, Quadtree, Octree? - Stack Overflow, https://stackoverflow.com/questions/99796/when-to-use-binary-space-partitioning-quadtree-octree
61. An evaluation of Kd-Trees vs Bounding Volume Hierarchy (BVH) acceleration structures in modern CPU architectures - SciELO, https://www.scielo.sa.cr/scielo.php?script=sci_arttext&pid=S0379-39822023000200086
62. Octree-based Collision Detection in iMSTK - Kitware, Inc., https://www.kitware.com/octree-collision-imstk/
63. Matth3wThomson/Octree: A simple 3d Physics Simulation created for a uni module - GitHub, https://github.com/Matth3wThomson/Octree
64. Frustum Culling - LearnOpenGL, https://learnopengl.com/Guest-Articles/2021/Scene/Frustum-Culling
65. A Recursive Approach for Octree Traversal, https://chiranjivi.tripod.com/octrav.html
66. An Adaptive Octree for Efficient Ray Tracing - Visualization and Computer Graphics, IEEE Transactions on, https://www.cs.drexel.edu/~david/Classes/Papers/IEEE_TOVCG95_v1n4.pdf
67. Interactive Isosurface Ray Tracing of Large Octree Volumes - Scientific Computing and Imaging Institute, https://www.sci.utah.edu/~wald/Publications/2006/OctIso/octiso.pdf
68. Efficient octree traversal, https://bertolami.com/files/octrees.pdf
69. Octree Algorithm, https://web.cs.wpi.edu/~matt/courses/cs563/talks/color_quant/CQoctree.html
70. (PDF) Towards Efficient Implementation of an Octree for a Large 3D Point Cloud, https://www.researchgate.net/publication/329603314_Towards_Efficient_Implementation_of_an_Octree_for_a_Large_3D_Point_Cloud
71. Towards Efficient Implementation of an Octree for a Large 3D Point Cloud - PMC, https://pmc.ncbi.nlm.nih.gov/articles/PMC6308722/
72. Hierarchical Data Structures (Octrees) for Big Data - YouTube, https://www.youtube.com/watch?v=NnJZUZx0xqM
73. 옥트리 기반의 해마의 국부적 형상 분석 - Korea Science, https://koreascience.kr/article/CFKO200411923025551.pdf
74. (PDF) Fast Out‐of‐Core Octree Generation for Massive Point Clouds - ResearchGate, https://www.researchgate.net/publication/343449632_Fast_Out-of-Core_Octree_Generation_for_Massive_Point_Clouds
75. OCTREE-BASED APPROACH FOR REAL-TIME 3D INDOOR MAPPING USING RGB-D VIDEO DATA, https://isprs-archives.copernicus.org/articles/XLVIII-1-W1-2023/183/2023/isprs-archives-XLVIII-1-W1-2023-183-2023.pdf
76. Accelerated Mapping and Illumination for a Point … - DSpace@EWHA, https://dspace.ewha.ac.kr/handle/2015.oak/270903
77. 이동로봇을 위한 SLAM 기술, http://icros.org/Newsletter/202201/5.%EB%A1%9C%EB%B4%87%EA%B8%B0%EC%88%A0%EB%A6%AC%EB%B7%B0.pdf
78. prime-slam/octreelib: Library for representing point clouds as OcTrees in SLAM. - GitHub, https://github.com/prime-slam/octreelib
79. Octree maps built by RDS-SLAM. | Download Scientific Diagram - ResearchGate, https://www.researchgate.net/figure/Octree-maps-built-by-RDS-SLAM_fig4_348368507
80. www.numberanalytics.com, https://www.numberanalytics.com/blog/ultimate-guide-to-octree-in-algorithm-design#:~:text=Geographic%20Information%20Systems%20(GIS)%3A,%2C%20tracking%2C%20and%20scene%20understanding.
81. View of Application of the Properties of an Organized Point Cloud in an Octree in Solving Geodetic Tasks - Journal of Electrical Systems, https://journal.esrgroups.org/jes/article/view/7491/5143
82. What Is Rapid Octree Meshing? - Ansys, https://www.ansys.com/blog/what-is-rapid-octree-meshing
83. Octree-Based Shifted Boundary Method for Multiphysics Simulations Using Linearized Navier-Stokes in Complex Geometries - ResearchGate, https://www.researchgate.net/publication/387670006_Octree-Based_Shifted_Boundary_Method_for_Multiphysics_Simulations_Using_Linearized_Navier-Stokes_in_Complex_Geometries
84. What’s the difference between a ‘regular’ octree and a ‘sparse voxel octree?’ - Reddit, https://www.reddit.com/r/VoxelGameDev/comments/16u132r/whats_the_difference_between_a_regular_octree_and/
85. Sparse voxel octree - Wikipedia, https://en.wikipedia.org/wiki/Sparse_voxel_octree
86. A Sparse Voxel Octree-Based Framework for Computing Solar Radiation Using 3D City Models - MDPI, https://www.mdpi.com/2220-9964/6/4/106
87. Efficient Sparse Voxel Octrees – Analysis, Extensions, and Implementation - Research at NVIDIA, https://research.nvidia.com/sites/default/files/pubs/2010-02_Efficient-Sparse-Voxel/laine2010tr1_paper.pdf
88. 라이다 점군의 효율적 검색을 위한 CUDA 기반 옥트리 알고리듬 구현 - 대한원격탐사학회지, https://kiss.kstudy.com/Detail/Ar?key=3649677
89. Fast Collision Detection Method with Octree-Based Parallel Processing in Unity3D - MDPI, https://www.mdpi.com/2673-4591/89/1/37
90. Sparse Voxel Octree, https://eisenwave.github.io/voxel-compression-docs/svo/svo.html
91. A Domain Adjusting Region Octree: Indexing a stream of unpredictable point cloud data for line-of-sight analysis - DiVA portal, http://www.diva-portal.org/smash/get/diva2:1895902/FULLTEXT01.pdf
92. [2306.05133] Octree-based hierarchical sampling optimization for the volumetric super-resolution of scientific data - arXiv, https://arxiv.org/abs/2306.05133
93. An autonomous navigation method for orchard mobile robots based on octree 3D point cloud optimization - PMC - PubMed Central, https://pmc.ncbi.nlm.nih.gov/articles/PMC11746033/
94. Octree-based 3D Gaussian Splatting for Robust Object-level 3D Reconstruction Under Strong Lighting - arXiv, https://arxiv.org/html/2406.18199v1
95. SIGGRAPH에서 시뮬레이션과 생성형 AI의 최신 발전 사항을 발표하는 NVIDIA Research, https://blogs.nvidia.co.kr/blog/siggraph-2024-ai-graphics-research/
96. [2406.08527] Optimized Feature Generation for Tabular Data via LLMs with Decision Tree Reasoning - arXiv, https://arxiv.org/abs/2406.08527
97. [자료구조] 5. 트리(Tree), https://levell1.github.io/data%20structure/Tree/
98. 3D모델링기초(2), https://www.kunjang.ac.kr/default/common/file_download.jsp?SITE_NUM=&MOD_NUM=720&bf_num=31443267
99. CG351-551 Quad and Oct-trees: Disadvantages of Octrees., http://euklid.mi.uni-koeln.de/c/mirror/www.cs.curtin.edu.au/units/cg351-551/notes/lect5j1.html
100. Mastering Octrees in Computational Geometry - Number Analytics, https://www.numberanalytics.com/blog/mastering-octrees-computational-geometry
101. (PDF) Bounding volume hierarchies versus Kd-trees on contemporary many-core architectures - ResearchGate, https://www.researchgate.net/publication/282678485_Bounding_volume_hierarchies_versus_Kd-trees_on_contemporary_many-core_architectures